/**
 * @author LKQ
 * @date 2022/1/14 12:14
 * @description 二分查找，由于连续子数组的乘积可能会溢出，所以将乘法变成对数加法
 */
public class FormalSolution {
    public static void main(String[] args) {
        FormalSolution solution = new FormalSolution();
        int[] nums = {10, 5, 2, 6};
        solution.numSubarrayProductLessThanK(nums, 100);
    }
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if (k == 0) {
            return 0;
        }
        double logk = Math.log(k);
        double[] prefix = new double[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefix[i+1] = prefix[i] + Math.log(nums[i]);
        }

        int ans = 0;
        for (int i = 0; i < prefix.length; i++) {
            int lo = i + 1, hi = prefix.length;
            while (lo < hi) {
                int mi = lo + (hi - lo) / 2;
                if (prefix[mi] < prefix[i] + logk - 1e-9) {
                    lo = mi + 1;
                } else {
                    hi = mi;
                }
            }
            ans += lo - i - 1;
        }
        return ans;
    }

}
